﻿/* @basic info
   Resolver: a simple c/c++-compiler-like resolver
   author: Zhengze Zhu (http://zhengze.eu.org)
   version: revision 3 (merged)

   this file is a manually merged version, with filename as a comment at start of each part
   
   NOTE: as entries for the "十行代码" activity, source.in is considered as the romantic part while this file in majority is the practical-use part, which provides useful calculation functions, but includes romantic parts as well.
*/

/* @copyright notice
   Copyright © 2023 Zhnegze Zhu

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

	   http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

/* @license content
								 Apache License
						   Version 2.0, January 2004
						http://www.apache.org/licenses/

   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION

   1. Definitions.

	  "License" shall mean the terms and conditions for use, reproduction,
	  and distribution as defined by Sections 1 through 9 of this document.

	  "Licensor" shall mean the copyright owner or entity authorized by
	  the copyright owner that is granting the License.

	  "Legal Entity" shall mean the union of the acting entity and all
	  other entities that control, are controlled by, or are under common
	  control with that entity. For the purposes of this definition,
	  "control" means (i) the power, direct or indirect, to cause the
	  direction or management of such entity, whether by contract or
	  otherwise, or (ii) ownership of fifty percent (50%) or more of the
	  outstanding shares, or (iii) beneficial ownership of such entity.

	  "You" (or "Your") shall mean an individual or Legal Entity
	  exercising permissions granted by this License.

	  "Source" form shall mean the preferred form for making modifications,
	  including but not limited to software source code, documentation
	  source, and configuration files.

	  "Object" form shall mean any form resulting from mechanical
	  transformation or translation of a Source form, including but
	  not limited to compiled object code, generated documentation,
	  and conversions to other media types.

	  "Work" shall mean the work of authorship, whether in Source or
	  Object form, made available under the License, as indicated by a
	  copyright notice that is included in or attached to the work
	  (an example is provided in the Appendix below).

	  "Derivative Works" shall mean any work, whether in Source or Object
	  form, that is based on (or derived from) the Work and for which the
	  editorial revisions, annotations, elaborations, or other modifications
	  represent, as a whole, an original work of authorship. For the purposes
	  of this License, Derivative Works shall not include works that remain
	  separable from, or merely link (or bind by name) to the interfaces of,
	  the Work and Derivative Works thereof.

	  "Contribution" shall mean any work of authorship, including
	  the original version of the Work and any modifications or additions
	  to that Work or Derivative Works thereof, that is intentionally
	  submitted to Licensor for inclusion in the Work by the copyright owner
	  or by an individual or Legal Entity authorized to submit on behalf of
	  the copyright owner. For the purposes of this definition, "submitted"
	  means any form of electronic, verbal, or written communication sent
	  to the Licensor or its representatives, including but not limited to
	  communication on electronic mailing lists, source code control systems,
	  and issue tracking systems that are managed by, or on behalf of, the
	  Licensor for the purpose of discussing and improving the Work, but
	  excluding communication that is conspicuously marked or otherwise
	  designated in writing by the copyright owner as "Not a Contribution."

	  "Contributor" shall mean Licensor and any individual or Legal Entity
	  on behalf of whom a Contribution has been received by Licensor and
	  subsequently incorporated within the Work.

   2. Grant of Copyright License. Subject to the terms and conditions of
	  this License, each Contributor hereby grants to You a perpetual,
	  worldwide, non-exclusive, no-charge, royalty-free, irrevocable
	  copyright license to reproduce, prepare Derivative Works of,
	  publicly display, publicly perform, sublicense, and distribute the
	  Work and such Derivative Works in Source or Object form.

   3. Grant of Patent License. Subject to the terms and conditions of
	  this License, each Contributor hereby grants to You a perpetual,
	  worldwide, non-exclusive, no-charge, royalty-free, irrevocable
	  (except as stated in this section) patent license to make, have made,
	  use, offer to sell, sell, import, and otherwise transfer the Work,
	  where such license applies only to those patent claims licensable
	  by such Contributor that are necessarily infringed by their
	  Contribution(s) alone or by combination of their Contribution(s)
	  with the Work to which such Contribution(s) was submitted. If You
	  institute patent litigation against any entity (including a
	  cross-claim or counterclaim in a lawsuit) alleging that the Work
	  or a Contribution incorporated within the Work constitutes direct
	  or contributory patent infringement, then any patent licenses
	  granted to You under this License for that Work shall terminate
	  as of the date such litigation is filed.

   4. Redistribution. You may reproduce and distribute copies of the
	  Work or Derivative Works thereof in any medium, with or without
	  modifications, and in Source or Object form, provided that You
	  meet the following conditions:

	  (a) You must give any other recipients of the Work or
		  Derivative Works a copy of this License; and

	  (b) You must cause any modified files to carry prominent notices
		  stating that You changed the files; and

	  (c) You must retain, in the Source form of any Derivative Works
		  that You distribute, all copyright, patent, trademark, and
		  attribution notices from the Source form of the Work,
		  excluding those notices that do not pertain to any part of
		  the Derivative Works; and

	  (d) If the Work includes a "NOTICE" text file as part of its
		  distribution, then any Derivative Works that You distribute must
		  include a readable copy of the attribution notices contained
		  within such NOTICE file, excluding those notices that do not
		  pertain to any part of the Derivative Works, in at least one
		  of the following places: within a NOTICE text file distributed
		  as part of the Derivative Works; within the Source form or
		  documentation, if provided along with the Derivative Works; or,
		  within a display generated by the Derivative Works, if and
		  wherever such third-party notices normally appear. The contents
		  of the NOTICE file are for informational purposes only and
		  do not modify the License. You may add Your own attribution
		  notices within Derivative Works that You distribute, alongside
		  or as an addendum to the NOTICE text from the Work, provided
		  that such additional attribution notices cannot be construed
		  as modifying the License.

	  You may add Your own copyright statement to Your modifications and
	  may provide additional or different license terms and conditions
	  for use, reproduction, or distribution of Your modifications, or
	  for any such Derivative Works as a whole, provided Your use,
	  reproduction, and distribution of the Work otherwise complies with
	  the conditions stated in this License.

   5. Submission of Contributions. Unless You explicitly state otherwise,
	  any Contribution intentionally submitted for inclusion in the Work
	  by You to the Licensor shall be under the terms and conditions of
	  this License, without any additional terms or conditions.
	  Notwithstanding the above, nothing herein shall supersede or modify
	  the terms of any separate license agreement you may have executed
	  with Licensor regarding such Contributions.

   6. Trademarks. This License does not grant permission to use the trade
	  names, trademarks, service marks, or product names of the Licensor,
	  except as required for reasonable and customary use in describing the
	  origin of the Work and reproducing the content of the NOTICE file.

   7. Disclaimer of Warranty. Unless required by applicable law or
	  agreed to in writing, Licensor provides the Work (and each
	  Contributor provides its Contributions) on an "AS IS" BASIS,
	  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
	  implied, including, without limitation, any warranties or conditions
	  of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
	  PARTICULAR PURPOSE. You are solely responsible for determining the
	  appropriateness of using or redistributing the Work and assume any
	  risks associated with Your exercise of permissions under this License.

   8. Limitation of Liability. In no event and under no legal theory,
	  whether in tort (including negligence), contract, or otherwise,
	  unless required by applicable law (such as deliberate and grossly
	  negligent acts) or agreed to in writing, shall any Contributor be
	  liable to You for damages, including any direct, indirect, special,
	  incidental, or consequential damages of any character arising as a
	  result of this License or out of the use or inability to use the
	  Work (including but not limited to damages for loss of goodwill,
	  work stoppage, computer failure or malfunction, or any and all
	  other commercial damages or losses), even if such Contributor
	  has been advised of the possibility of such damages.

   9. Accepting Warranty or Additional Liability. While redistributing
	  the Work or Derivative Works thereof, You may choose to offer,
	  and charge a fee for, acceptance of support, warranty, indemnity,
	  or other liability obligations and/or rights consistent with this
	  License. However, in accepting such obligations, You may act only
	  on Your own behalf and on Your sole responsibility, not on behalf
	  of any other Contributor, and only if You agree to indemnify,
	  defend, and hold each Contributor harmless for any liability
	  incurred by, or claims asserted against, such Contributor by reason
	  of your accepting any such warranty or additional liability.

   END OF TERMS AND CONDITIONS

   APPENDIX: How to apply the Apache License to your work.

	  To apply the Apache License to your work, attach the following
	  boilerplate notice, with the fields enclosed by brackets "[]"
	  replaced with your own identifying information. (Don't include
	  the brackets!)  The text should be enclosed in the appropriate
	  comment syntax for the file format. We also recommend that a
	  file or class name and description of purpose be included on the
	  same "printed page" as the copyright notice for easier
	  identification within third-party archives.

   Copyright [yyyy] [name of copyright owner]

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

	   http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#define DEBUG // global debug sign

/*Basics.h*/

#ifndef BASICS_H
#define BASICS_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Declarations

typedef struct _SingleLinkNode
{
	char data[51];
	struct _SingleLinkNode* suffix;
} SingleLinkNode, Node;

typedef struct _LinkStack
{
	Node* top;
} LinkStack;

void LSConstruct(LinkStack* pls);
void LSDestruct(LinkStack* pls);
int LSPush(LinkStack* pls, const char* nodeData);
int LSPop(LinkStack* pls, char* nodeData/* = nullptr*/);
const char* LSTop(LinkStack* pls, char* nodeData/* = nullptr*/);
int LSEmpty(LinkStack* pls);
void LSClear(LinkStack* pls);

typedef struct _LinkQueue
{
	Node* front;
	Node* end;
} LinkQueue;

void LQConstruct(LinkQueue* plq);
void LQDestruct(LinkQueue* plq);
int LQPush(LinkQueue* plq, const char* nodeData);
int LQPop(LinkQueue* plq, char* nodeData/* = nullptr*/);
const char* LQFront(LinkQueue* plq, char* nodeData/* = nullptr*/);
int LQEmpty(LinkQueue* plq);
void LQClear(LinkQueue* plq);

// Implementations

void LSConstruct(LinkStack* pls)
{
	pls->top = 0;
}

void LSDestruct(LinkStack* pls)
{
	LSClear(pls);
}

int LSPush(LinkStack* pls, const char* nodeData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (!newNode) {
#ifdef DEBUG
		printf("memory allocation failed\n");
#endif
		return 0;
	}
	strcpy(newNode->data, nodeData);
	newNode->suffix = pls->top;
	pls->top = newNode;
	return 1;
}

int LSPop(LinkStack* pls, char* nodeData/* = nullptr*/)
{
	if (pls->top == 0) {
#ifdef DEBUG
		printf("pop stack failed: empty");
#endif
		return 0;
	}
	Node* delNode = pls->top;
	pls->top = pls->top->suffix;
	if (nodeData)
	{
		strcpy(nodeData, delNode->data);
	}
	free(delNode);
	return 1;
}

const char* LSTop(LinkStack* pls, char* nodeData/* = nullptr*/)
{
	if (pls->top)
	{
		if (nodeData) {
			strcpy(nodeData, pls->top->data);
		}
		return pls->top->data;
	}
	else
	{
		return 0;
	}
}

int LSEmpty(LinkStack* pls)
{
	return !pls->top;
}

void LSClear(LinkStack* pls)
{
	while (LSEmpty(pls) ? 0 : LSPop(pls, 0)) {}
}

void LQConstruct(LinkQueue* plq)
{
	plq->front = 0;
	plq->end = 0;
}

void LQDestruct(LinkQueue* plq)
{
	LQClear(plq);
}

int LQPush(LinkQueue* plq, const char* nodeData)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (!newNode) {
#ifdef DEBUG
		printf("memory allocation failed\n");
#endif
		return 0;
	}
	strcpy(newNode->data, nodeData);
	if (plq->end)
	{
		newNode->suffix = plq->end->suffix;
		plq->end = plq->end->suffix = newNode;
	}
	else
	{
		newNode->suffix = 0;
		plq->end = plq->front = newNode;
	}
	return 1;
}

int LQPop(LinkQueue* plq, char* nodeData/* = nullptr*/)
{
	if (!plq->front) {
#ifdef DEBUG
		printf("pop queue failed: empty\n");
#endif
		return 0;
	}
	Node* delNode = plq->front;
	plq->front = plq->front->suffix;
	if (!plq->front)
	{
		plq->end = 0;
	}
	if (nodeData)
	{
		strcpy(nodeData, delNode->data);
	}
	free(delNode);
	return 1;
}

const char* LQFront(LinkQueue* plq, char* nodeData/* = nullptr*/)
{
	if (plq->front)
	{
		if (nodeData) {
			strcpy(nodeData, plq->front->data);
		}
		return plq->front->data;
	}
	else
	{
		return 0;
	}
}

int LQEmpty(LinkQueue* plq)
{
	return !plq->front;
}

void LQClear(LinkQueue* plq)
{
	while (LQEmpty(plq) ? 0 : LQPop(plq, 0)) {}
}

double Add(double lo, double ro)
{
	return lo + ro;
}

double Sub(double lo, double ro)
{
	return lo - ro;
}

double Mul(double lo, double ro)
{
	return lo * ro;
}

double Div(double lo, double ro)
{
	return lo / ro;
}

double Above(double lo, double ro)
{
	return lo > ro;
}

double Below(double lo, double ro)
{
	return lo < ro;
}

double Not(double lo, double reserved)
{
	return !lo;
}

double And(double lo, double ro)
{
	return lo && ro;
}

double Or(double lo, double ro)
{
	return lo || ro;
}

typedef struct _OperatorProperties
{
	short priorityInsideStack;
	short priorityOutsideStack;
	short numberOfOperand;
	void* func;
} OperatorProperties;

typedef struct _Operator
{
	char op[11];
	OperatorProperties prop;
} Operator;

/*
* priorities: priority inside/outside stack
*
* = operator:		priorities are always 0 (lowest priority)
* ( operator:		priority inside stack = 1 (second lowest priority)
*					priority outside stack = highest priority
* ) operator:		priority inside stack = highest priority
*					priority outside stack = 1 (second lowest priority)
* normal operators:	minimum priority is 2 (third lowest priority)
*					maximum priority is highest priority - 1
*					priority inside stack = priority outside stack + 1
*					priorities of operators of different types mustn't overlap
*/

#define NUM_OPERATOR sizeof(operators) / sizeof(Operator)

Operator operators[] = {
	{";",	{0,	0,	-1,	0}},
	{"(",	{1,	14,	1,	0}},
	{")",	{14,1,	1,	0}},
	{"!",	{13,12,	1,	Not}},
	{"*",	{11,10,	2,	Mul}},
	{"/",	{11,10,	2,	Div}},
	{"+",	{9,	8,	2,	Add}},
	{"-",	{9,	8,	2,	Sub}},
	{">",	{7,	6,	2,	Above}},
	{"<",	{7,	6,	2,	Below}},
	{"&",	{5,	4,	2,	And}},
	{"|",	{3,	2,	2,	Or}}
};

OperatorProperties GetOperatorProps(const char* op)
{
	for (int i = 0; i < NUM_OPERATOR; ++i)
	{
		if (strcmp(op, operators[i].op) == 0)
		{
			return operators[i].prop;
		}
	}
	return (OperatorProperties) { -1, -1, -1, 0 };
}

#endif

/*CheckFunctions.h*/

#ifndef CHECK_FUNCTIONS_H
#define CHECK_FUNCTIONS_H

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int CheckBrackets(const char* expression, int* numL, int* numR)
{
	int leftbrcktct = 0;
	int rightbrcktct = 0;

	const int explen = strlen(expression);
	for (int i = 0; i < explen; ++i)
	{
		if (expression[i] == '(')
		{
			++leftbrcktct;
		}
		else
		{
			if (expression[i] == ')')
			{
				++rightbrcktct;
			}
		}
	}

	if (numL && numR)
	{
		*numL = leftbrcktct;
		*numR = rightbrcktct;
	}
	return leftbrcktct - rightbrcktct;
}

typedef struct _Range
{
	int lowerBound;
	int upperBound;
} Range;

void swap(int* a, int* b)
{
	(*a) = (*a) ^ (*b);
	(*b) = (*a) ^ (*b);
	(*a) = (*a) ^ (*b);
}

/*
* range bounds:
* >= 0: sequential
* <	 0: reverse, '\0' included
* range = [lower bound, upper bound)
* lower bound == upper bound -> range = [lower bound, end of string)
*
* mode:
* strict: pure operater
* loose	: start with operator
*/
int CheckOperand(const char* originalExpression, Range range/* = {0, 0}*/, int strict/* = true*/)
{
	if (range.lowerBound == range.upperBound)
	{
		range.upperBound = strlen(originalExpression);
	}
	if (range.lowerBound < 0)
	{
		range.lowerBound = strlen(originalExpression) + 1 + range.lowerBound;
	}
	if (range.upperBound < 0)
	{
		range.upperBound = strlen(originalExpression) + 1 + range.upperBound;
	}
	if (range.upperBound < range.lowerBound)
	{
		swap(&(range.lowerBound), &(range.upperBound));
	}
	char* expression = (char*)originalExpression + range.lowerBound;
	if (expression[0] == '-') // if previous token exists and is an operand, this is a reduction sign. otherwise, this is a negative sign.
	{
		char* expressionContext = (char*)originalExpression + range.lowerBound - 1;
		while (expressionContext - originalExpression >= 0 && isspace(*expressionContext))
		{
			--expressionContext;
		}
		if (expressionContext - originalExpression >= 0)
		{
			int isNeg = 0;
			for (int i = 0; i < NUM_OPERATOR; ++i)//(const auto& op : operators)
			{
				if (expressionContext - originalExpression + 1 >= strlen(operators[i].op)
					&& strncmp(expressionContext - strlen(operators[i].op) + 1, operators[i].op, strlen(operators[i].op)) == 0)
				{
					isNeg = 1;
				}
			}
			if (!isNeg)
			{
				return 0;
			}
		}
	}
	long expLength = range.upperBound - range.lowerBound, offset = 0;

	if (expression[0] == '-')
	{
		if (expLength == 1)
			return 0;
		offset = 1;
	}

	for (; offset < expLength; ++offset)
	{
		if (!(isdigit(expression[offset]) || expression[offset] == '.'))
		{
			if (!strict)
			{
				return offset/* + (expression[offset] == 'i' ? 1 : 0)*/;
			}
			else/* if (!(offset == expLength - 1 && expression[offset] == 'i'))*/
			{
				return 0;
			}
		}
	}

	return offset;
}

/*
* range bounds:
* >= 0: sequential
* <	 0: reverse, '\0' included
* range = [lower bound, upper bound)
* lower bound == upper bound -> range = [lower bound, end of string)
*
* mode:
* strict: pure operater
* loose	: start with operator
*/
int CheckOperator(const char* originalExpression, Range range/* = {0, 0}*/, int strict/* = true*/)
{
	if (range.lowerBound == range.upperBound)
	{
		range.upperBound = strlen(originalExpression);
	}
	if (range.lowerBound < 0)
	{
		range.lowerBound = strlen(originalExpression) + 1 + range.lowerBound;
	}
	if (range.upperBound < 0)
	{
		range.upperBound = strlen(originalExpression) + 1 + range.upperBound;
	}
	if (range.upperBound < range.lowerBound)
	{
		swap(&(range.lowerBound), &(range.upperBound));
	}
	char* expression = (char*)originalExpression + range.lowerBound;
	for (int i = 0; i < NUM_OPERATOR; ++i)//(const auto& op : operators)
	{
		if (strncmp(expression, operators[i].op, strlen(operators[i].op)) == 0
			&& (strict ? range.upperBound - range.lowerBound == strlen(operators[i].op) : 1))
		{
			return strlen(operators[i].op);
		}
	}

	return 0;
}

#endif

/*Resolver.h*/

#ifndef RESOLVER_H
#define RESOLVER_H

#include <stdlib.h>
#include <math.h>

int Infix2Postfix(LinkQueue* queue)
{
	LinkStack stack;
	LSConstruct(&stack);
	char exp[51];
	LQPop(queue, exp);
	if (!LSPush(&stack, ";"))
	{
		LSDestruct(&stack);
		return 0;
	}
	while (!LSEmpty(&stack))
	{
		if (!CheckOperator(exp, (Range) { 0, 0 }, 1))
		{
			if (!LQPush(queue, exp))
			{
				LSDestruct(&stack);
				return 0;
			}
			LQPop(queue, exp);
		}
		else if (GetOperatorProps(LSTop(&stack, 0)).priorityInsideStack < GetOperatorProps(exp).priorityOutsideStack)
		{
			if (!LSPush(&stack, exp))
			{
				LSDestruct(&stack);
				return 0;
			}
			LQPop(queue, exp);
		}
		else if (GetOperatorProps(LSTop(&stack, 0)).priorityInsideStack > GetOperatorProps(exp).priorityOutsideStack)
		{
			if (!LQPush(queue, LSTop(&stack, 0)))
			{
				LSDestruct(&stack);
				return 0;
			}
			LSPop(&stack, 0);
		}
		else // if (GetOperatorProps(LSTop(&stack, 0)).priorityInsideStack == GetOperatorProps(exp).priorityOutsideStack)
		{
			if (strcmp(LSTop(&stack, 0), "(") == 0)
			{
				LQPop(queue, exp);
			}
			LSPop(&stack, 0);
		}
	}
	LSDestruct(&stack);
	return 1;
}

typedef double (*lpFunc) (double dbleft, double dbright);

void compute(char** operands, const char* strOperator)
{
	double ans = 0, dbleft, dbright = -1;
	int numOperand = GetOperatorProps(strOperator).numberOfOperand;
	if (numOperand == 2)
	{
		dbright = atof(operands[2]);
	}
	dbleft = atof(operands[1]);
	ans = ((lpFunc)GetOperatorProps(strOperator).func)(dbleft, dbright);
	sprintf(operands[0], "%lf", ans);
	return;
}

typedef struct _VarValPair
{
	char type[11];
	char var[51];
	char val[51];
} VarValPair;

/*
* operation:
*	set: operation = 1;
*	get: operation = 2;
*	clr: operation = 3;
*/
int VarList(const char* type, const char* var, char* val, short operation)
{
	static int listSize = 0;
	static VarValPair* varList[300];

	int retVal = 0;

	switch (operation)
	{
	case 1:
		for (int i = 0; i < listSize; ++i)
		{
			if (strcmp(var, varList[i]->var) == 0)
			{
				if (strcmp(varList[i]->type, "int") == 0)
				{
					sprintf(val, "%ld", (long)ceil(atof(val))); // use long to avoid data loss
				}
				strcpy(varList[i]->val, val);
				return retVal;
			}
		}
		if (!type)
		{
			retVal = 2;
		}
		else
		{
			if (strcmp(type, "int") == 0)
			{
				sprintf(val, "%ld", (long)ceil(atof(val))); // use long to avoid data loss
			}
			varList[listSize] = (VarValPair * )malloc(sizeof(VarValPair));
			if (varList[listSize])
			{
				strcpy(varList[listSize]->type, type);
				strcpy(varList[listSize]->var, var);
				strcpy(varList[listSize]->val, val);
				++listSize;
			}
			else
			{
				retVal = 1;
			}
		}
		break;
	case 2:
		for (int i = 0; i < listSize; ++i)
		{
			if (strcmp(var, varList[i]->var) == 0)
			{
				strcpy(val, varList[i]->val);
				return retVal;
			}
		}
		strcpy(val, "0");
		break;
	case 3:
		for (int i = 0; i < listSize; ++i)
		{
			free(varList[i]);
		}
		listSize = 0;
		break;
	}
	return retVal;
}

int strreplace(const char* in, char* out, int outlen, const char* oldstr, const char* newstr) {
	--outlen;
	int inlen = strlen(in);
	int oldlen = strlen(oldstr);
	int newlen = strlen(newstr);
	int i, j;
	int count = 0;

	if (inlen > outlen) {
		return 0;
	}

	for (i = 0, j = 0; i < inlen; ) {
		if (strncmp(in + i, oldstr, oldlen) == 0) {
			if (inlen + (newlen - oldlen) * (count + 1) <= outlen) {
				strncpy(out + j, newstr, newlen);
				j += newlen;
				count++;
			}
			else {
				strncpy(out + j, oldstr, oldlen);
				j += oldlen;
			}
			i += oldlen;
		}
		else {
			if (j + 1 <= outlen) {
				out[j++] = in[i++];
			}
			else {
				break;
			}
		}
	}
	out[j] = '\0';
	return count;
}

void RemoveSpace(char* exp)
{
	char* newExp = (char*)malloc(sizeof(char) * (strlen(exp) + 1));
	strreplace(exp, newExp, strlen(exp) + 1, " ", "");
	strcpy(exp, newExp);
	free(newExp);
}

void SplitRightExp(const char* exp, char** tokens, int* sizeToken)
{
	RemoveSpace((char*)exp);
	int lenOperand = 0, lenOperator = 0;
	*sizeToken = 0;
	int offset = 0;
	do {
		lenOperand = CheckOperand(exp, (Range) { offset, offset }, 0);
		if (!lenOperand)
		{
			lenOperator = CheckOperator(exp, (Range) { offset, offset }, 0);
			if (lenOperator)
			{
				tokens[*sizeToken] = malloc(sizeof(char) * 51);
				strncpy(tokens[*sizeToken], exp + offset, lenOperator);
				tokens[*sizeToken][lenOperator] = 0;
				++(*sizeToken);
				offset += lenOperator;
			}
			else
			{
				lenOperand = 1;
				for (; !CheckOperator(exp, (Range) { offset + lenOperand, offset + lenOperand }, 0); ++lenOperand)
				{
				}
				tokens[*sizeToken] = malloc(sizeof(char) * 51);
				strncpy(tokens[*sizeToken], exp + offset, lenOperand);
				tokens[*sizeToken][lenOperand] = 0;
				++(*sizeToken);
				offset += lenOperand;
			}
		}
		else
		{
			tokens[*sizeToken] = (char*)malloc(sizeof(char) * 51);
			strncpy(tokens[*sizeToken], exp + offset, lenOperand);
			tokens[*sizeToken][lenOperand] = 0;
			++(*sizeToken);
			offset += lenOperand;
		}
	} while (offset < strlen(exp));
	return;
}

int SplitExp(const char* oriExp, char** tokens)
{
	char* exp = (char*)oriExp;
	if (strncmp(exp, "float ", 6) == 0)
	{
		tokens[0] = (char*)malloc(sizeof(char) * 6);
		strcpy(tokens[0], "float");
		exp += 6;
	}
	else if (strncmp(exp, "int ", 4) == 0)
	{
		tokens[0] = (char*)malloc(sizeof(char) * 4);
		strcpy(tokens[0], "int");
		exp += 4;
	}
	else
	{
		tokens[0] = (char*)malloc(sizeof(char));
		tokens[0] = 0;
	}
	int lenExp = 0;
	for (; (lenExp < strlen(exp)) && !(isspace(exp[lenExp]) || exp[lenExp] == '=' || exp[lenExp] == ';'); ++lenExp) { }
	if (!lenExp || lenExp == strlen(exp))
	{
		return 0;
	}
	tokens[1] = (char*)malloc(sizeof(char) * (lenExp + 1));
	strncpy(tokens[1], exp, lenExp);
	tokens[1][lenExp] = 0;
	exp += lenExp;
	RemoveSpace(exp);
	if (strcmp(exp, ";") != 0)
	{
		if (exp[0] == '=')
		{
			++exp;
			tokens[2] = (char*)malloc(sizeof(char) * (strlen(exp) + 1));
			strcpy(tokens[2], exp);
		}
		return 1;
	}
	tokens[2] = (char*)malloc(sizeof(char) * 3);
	strcpy(tokens[2], "0;");
	return 1;
}

int resolver(const char* resolveFromFile, const char* outputToFile)
{
	int retVal = -1;
	FILE* sourceFile = 0;
	if (resolveFromFile && strlen(resolveFromFile))
	{
		sourceFile = fopen(resolveFromFile, "r");
		if (!sourceFile)
		{
			printf("warning: operation: cannot open source file. use standard input as source\n");
		}
	}
	FILE* destFile = 0;
	if (outputToFile && strlen(outputToFile))
	{
		destFile = fopen(outputToFile, "a");
		if (!destFile)
		{
			printf("warning: operation: cannot open output file. use standard output as output\n");
		}
	}
	LinkStack stack;
	LSConstruct(&stack);
	LinkQueue queue;
	LQConstruct(&queue);
	char* generalTokens[3] = { 0, 0, 0 };
	char* rightExpTokens[300];
	int curLine = 0;

	do
	{
		char exp[301] = "";
		if (sourceFile)
		{
			fgets(exp, 300, sourceFile);
			exp[((int)strlen(exp) - 1) > 0 ? ((int)strlen(exp) - 1) : 0] = 0;
			if (feof(sourceFile))
			{
				strcpy(exp, "quit();");
			}
		}
		else
		{
			scanf("%[^\f\n\r\t\v]", exp);
			getchar();
		}
		++curLine;
		if (!strlen(exp) || strncmp(exp, "//", 2) == 0)
		{
			goto cleanUp;
		}
		if (exp[strlen(exp) - 1] != ';')
		{
			printf("line %d: syntax error: expect \";\" at end of expression\n", curLine);
			retVal = 0;
			goto cleanUp;
		}
		if (strcmp(exp, "quit();") == 0)
		{
			retVal = 1;
			goto cleanUp;
		}
		int numBrackets[2] = { 0, 0 };
		if (CheckBrackets(exp, &numBrackets[0], &numBrackets[1]) != 0)
		{
			printf("line %d: syntax error: brackets not matched\n", curLine);
			printf("line %d: stats: %d left bracket(s) and %d right bracket(s)\n", curLine, numBrackets[0], numBrackets[1]);
			int unmatched = numBrackets[0] - numBrackets[1];
			if (unmatched < 0)
			{
				printf("\t%d unmatched right bracket(s)\n", -unmatched);
			}
			else // if (unmatched > 0)
			{
				printf("\t%d unmatched left bracket(s)\n", unmatched);
			}
			retVal = 0;
			goto cleanUp;
		}
		if (strncmp(exp, "print(", 6) == 0)
		{
			if (exp[6] == '\"' && exp[strlen(exp) - 3] == '\"')
			{
				exp[strlen(exp) - 3] = 0;
				if (!destFile)
				{
					printf("%s\n", exp + 7);
				}
				else
				{
					fprintf(destFile, "%s", exp + 7);
				}
				goto cleanUp;
			}
			else
			{
				exp[5] = '=';
				exp[strlen(exp) - 2] = ';';
				exp[strlen(exp) - 1] = 0;
			}
		}
		if (!SplitExp(exp, generalTokens))
		{
			printf("line %d: syntax error: token expected between %s and end of expression\n", curLine, strlen(generalTokens[0]) ? generalTokens[0] : "start of expression");
			retVal = 0;
			goto cleanUp;
		}
		int rightExpTokenSize = 0;
		SplitRightExp(generalTokens[2], rightExpTokens, &rightExpTokenSize);
		for (int i = 0; i < rightExpTokenSize; ++i)
		{
			if (!LQPush(&queue, rightExpTokens[i]))
			{
				printf("line %d: runtime error: cannot allocate memory in queue\n", curLine);
				retVal = 0;
				goto cleanUp;
			}
			free(rightExpTokens[i]);
		}
		rightExpTokenSize = 0;

		if (!Infix2Postfix(&queue))
		{
			printf("line %d: runtime error: cannot allocate memory in stack\n", curLine);
			retVal = 0;
			goto cleanUp;
		}

		while (!LQEmpty(&queue))
		{
			if (!CheckOperator(LQFront(&queue, 0), (Range) { 0, 0 }, 0))
			{
				if (!LSPush(&stack, LQFront(&queue, 0)))
				{
					printf("line %d: runtime error: cannot allocate memory in stack\n", curLine);
					retVal = 0;
					goto cleanUp;
				}
			}
			else
			{
				short numOperand = GetOperatorProps(LQFront(&queue, 0)).numberOfOperand;
				char* operands[3] = { 0, 0, 0 }; // answer, leftOperand[, rightOperand]
				if (numOperand == 1)
				{
					if (LSEmpty(&stack))
					{
						printf("line %d: runtime error: operand not found\n", curLine);
						retVal = 0;
						goto cleanUp;
					}
				}

				if (numOperand == 2)
				{
					if (LSEmpty(&stack))
					{
						printf("line %d: runtime error: right operand not found\n", curLine);
						retVal = 0;
						goto cleanUp;
					}

					operands[2] = (char*)malloc(sizeof(char) * 51);
					LSPop(&stack, operands[2]);
					if (!CheckOperand(operands[2], (Range) { 0, 0 }, 1))
					{
						char tempVar[51];
						strcpy(tempVar, operands[2]);
						VarList("", tempVar, operands[2], 2);
					}

					if (LSEmpty(&stack))
					{
						printf("line %d: runtime error: left operand not found\n", curLine);
						retVal = 0;
						goto cleanUp;
					}
				}

				operands[1] = (char*)malloc(sizeof(char) * 51);
				LSPop(&stack, operands[1]);
				if (!CheckOperand(operands[1], (Range) { 0, 0 }, 1))
				{
					char tempVar[51];
					strcpy(tempVar, operands[1]);
					VarList("", tempVar, operands[1], 2);
				}
				operands[0] = (char*)malloc(sizeof(char) * 51);
				compute(operands, LQFront(&queue, 0));
				if (!LSPush(&stack, operands[0]))
				{
					printf("line %d: runtime error: cannot allocate memory in stack\n", curLine);
					retVal = 0;
					goto cleanUp;
				}
				for (int i = 0; i < 3; ++i)
				{
					if (operands[i])
					{
						free(operands[i]);
					}
				}
			}
			LQPop(&queue, 0);
		}

		if (strncmp(generalTokens[1], "print", 6) == 0)
		{
			if (!CheckOperand(LSTop(&stack, 0), (Range) { 0, 0 }, 1))
			{
				char tempVar[51];
				VarList("", LSTop(&stack, 0), tempVar, 2);
				if (outputToFile && strlen(outputToFile))
				{
					if (!destFile)
					{
						printf("%s\n", tempVar);
					}
					else
					{
						fprintf(destFile, "%s", tempVar);
					}
				}
				else
				{
					printf("%s\n", tempVar);
				}
			}
			else
			{
				if (outputToFile && strlen(outputToFile))
				{
					if (!destFile)
					{
						printf("%s\n", LSTop(&stack, 0));
					}
					else
					{
						fprintf(destFile, "%s", LSTop(&stack, 0));
					}
				}
				else
				{
					printf("%s\n", LSTop(&stack, 0));
				}
			}
		}
		else
		{
			int valListRet = VarList(generalTokens[0], generalTokens[1], (char*)LSTop(&stack, 0), 1);
			switch (valListRet)
			{
			case 1:
				printf("line %d: runtime error: cannot allocate memory when assigning %s to %s\n", curLine, LSTop(&stack, 0), generalTokens[1]);
				retVal = 0;
				goto cleanUp;
			case 2:
				printf("line %d: runtime error: undefined identifier %s: assignment \" = %s;\" failed", curLine, generalTokens[1], LSTop(&stack, 0));
				break;
			}
		}
		cleanUp: // yes, we DO HATE "goto lable;"s. but duplicating cleanup code is even worse.
		for (int i = 0; i < 3; ++i)
		{
			free(generalTokens[i]);
			generalTokens[i] = 0;
		}
		LSClear(&stack); // we should have "LSPop(&stack, 0);"-ed first. but as long as we have "LSClear(&stack);", we don't need the popping anymore.
		LQClear(&queue);
	} while (retVal < 0); // loop while return value not set
	LSDestruct(&stack);
	LQDestruct(&queue);
	VarList(0, 0, 0, 3);
	if (sourceFile && fclose(sourceFile) != 0)
	{
		printf("operation error: cannot close source file\n");
		retVal = 0;
	}
	if (destFile && fclose(destFile) != 0)
	{
		printf("warning: operation: cannot close output file\n");
		retVal = 0;
	}
	return retVal;
}

/*
* types: int, float
* sytax:
*	define (initialized with default value 0 if no initialization): int a = 5;
*	assign: a = a & 2;
*	print pure text to output: print("5 & 2 = ");
*	print value of expression to output: print(a);
*	comment: // above code should output 5 & 2 = 1, which can be interpret as "I love U" in Chinese when "&" marks the following content as verb and "=" marks the following content as object
*	quit resolver: quit();
* notes:
*	only one definition / assignment / operation per line
*	when there is no "quit();" at end of source file, one will be automatically added
*/

#endif

/*Resolver.c*/

// the following is just an example. to use stdin/stdout, pass an empty string or 0 to the corresponding parameter.
int main()
{
	if (!resolver("source.in", "output.txt")) // source.in is the input for resolver here
	{
		printf("resolver exit with an error");
	}
	return 0;
}